/*
 * @lc app=leetcode.cn id=151 lang=swift
 *
 * [151] 翻转字符串里的单词
 */

// @lc code=start
class Solution151 {
    // 先将单词翻转。然后将整体翻转。
    func reverseWords(_ s: String) -> String {
        // 去除不必要的空格
        var sChars = removeSpace(s)
        // 先整体翻转
        reverseRange(&sChars, start: 0, end: sChars.count - 1)
        // 逐个单词翻转
        reverseAllWords(&sChars, end: sChars.count - 1)
        var str = ""
        for i in 0..<sChars.count {
            str.append(sChars[i])
        }
        return str
    }
    // 移除空格(首位空格，中间多余的空格)
    func removeSpace(_ s: String) -> [Character] {
        var sChars = [Character]()
        var space = true
        for c in s {
            if c != " " {
                sChars.append(c)
                space = false
            } else {
                if space == false {
                    sChars += " "
                    space = true
                }
            }
        }
        if space == true {
            sChars.removeLast()
        }
        return sChars
    }
    // 在逐个单词翻转
    func reverseAllWords(_ sChars: inout [Character], end: Int) {
        var slow = 0
        var fast = 0
        while fast <= end {
            if sChars[fast] == " " {
                reverseRange(&sChars, start: slow, end: fast - 1)
                fast += 1
                slow = fast
            } else {
                fast += 1
            }
        }
        reverseRange(&sChars, start: slow, end: fast - 1)
    }
    func reverseRange(_ sChars:inout [Character], start: Int, end: Int) {
        guard start <= end else {
            return
        }
        var slow = start
        var fast = end
        while slow < fast {
            let tmp = sChars[slow]
            sChars[slow] = sChars[fast]
            sChars[fast] = tmp
            slow += 1
            fast -= 1
        }
    }
    
    static func test() {
        let solution = Solution151()
        let s = "the sky is blue"
        let result = solution.reverseWords(s)
        print(result)
    }
}
// @lc code=end

